/**
 * describe:
 *
 * @author chaP
 * @date 2019/01/21
 */
package CodingTest.AC20190121;

/**
 * 编写一个程序，找到两个单链表相交的起始节点。

 如下面的两个链表：





 */
public class getIntersectionNode {
    class ListNode{
        int val;
        ListNode next;
        ListNode(int x){
            val  = x;
            next = null;
        }
    }

    /**
     *
     * 方法一：高手的解决方法：画个图一目了然，把两个链表规整为相同长度
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        /**
         *  定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
         两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
         */
        if(headA == null || headB == null)
            return null;
        ListNode pa = headA;
        ListNode pb = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
            while(pa != pb){
                pa = pa ==null ? headB:pa.next;
                pb = pb ==null ? headA:pb.next;
            }
            return pa;
    }

    /**
     * 自己的思路，计算长度差，长度大的先走，当两个链表长度一致时，两个链表同时走
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;
        int Alen = 1;
        int Blen = 1;
        ListNode pa = headA;
        ListNode pb = headB;
        while(pa.next != null){
            pa = pa.next;
            Alen ++;
        }
        while(pb.next != null){
            pb = pb.next;
            Blen ++;
        }
        int dis = 0;
        if(Alen >= Blen){
            dis = Alen - Blen;
            for(int i = 0;i<dis;i++)
                headA = headA.next;
        }else{
            dis = Blen - Alen;
            for(int i = 0;i<dis;i++)
                headB = headB.next;
        }
        while(headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        return headA;

    }}

